/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/super-pow
   @Language: C++
   @Datetime: 19-06-19 17:21
   */

// Method 1, Time 24ms
class Solution {
public:
	int superPow(int a, vector<int>& b) {
		a%=1337;
		int a10[11]={1}, res=1;
		for(int i=0; i++<10; a10[i]=(a10[i-1]*a)%1337);
		for(int i=b.size(); i--;){
			res=(res*a10[b[i]])%1337;
			for(int j=0; j++<10; a10[j]=(a10[j-1]*a10[10])%1337);
		}
		return res;
	}
};

// Method 2, Time 12ms
class Solution {
	int powmod(int a, int n, int m){
		int res=1;
		for(; n; a=(a*a)%m, n>>=1)
			if(n&1) res=(res*a)%m;
		return res;
	}
public:
	int superPow(int a, vector<int>& b) {
		int res=1;
		for(int i=b.size(), am=a%1337; i--; am=powmod(am,10,1337))
			res=(res*powmod(am,b[i],1337))%1337;
		return res;
	}
};
